1. Field of the Invention
This invention pertains generally to Medium Access Control protocol implementations. More particularly, the invention is a Medium Access Control protocol and method for use in a centrally managed network system at the Medium Access Control layer, which improves the throughput of protocol messages, reduces the latency of data transmissions and provides a set of failure management methods.
2. The Prior Art
Presently, there are numerous ways to provide communication algorithms between devices participating in a network offering various levels of reliability and effectiveness. Likewise, various protocol schemes have been developed to provide various networking services to such network devices.
In an effort to standardize protocols in network communication, the International Standards Organization (ISO) developed the Open Systems Interconnection (OSI) reference model. The OSI reference model deals with connecting systems that are open for communication with other systems and includes seven layers of network services including the Application or xe2x80x9chighestxe2x80x9d layer, the Presentation layer below the Application layer, the Session layer below the Application layer, the Transport layer below the Session layer, the Network layer below the Transport layer, the Data Link layer below the Network layer, and the Physical or xe2x80x9clowestxe2x80x9d layer below the Data Link layer.
The Data Link Layer is designed to offer various services to the Network layer. The principal service that the Data Link layer provides to the Network layer is transferring data from the Network layer of a source device to the Network layer on the destination or target device. The usual approach is for the Data Link layer to break up the bit stream into discrete blocks of bits, compute a checksum for each block, transmit the block along with the checksum to the target device in the form of a packet. When a packet arrives at the target device, the checksum is recomputed for the received block. If the newly computed checksum is different from the checksum provided by the source device, the Data Link layer identifies that an error has occurred and an error-recovery process is invoked.
At the Medium Access Control (MAC) sublayer of the Data Link layer, protocols are used to solve the issue of which network device gets to use the broadcast channel when there is competition for it. The MAC layer is particularly important in Local Area Networks (LANs) where the number of network devices competing for the communication channel may comprise hundreds of devices.
One algorithm devised to provide MAC layer services is the ALOHA system which comprises a xe2x80x9cregularxe2x80x9d form and a xe2x80x9cslottedxe2x80x9d form. In the regular ALOHA framework packet transmissions can occur anytime, while the slotted ALOHA framework divides time into discrete time slots in which all packet transmissions must be synchronized, where the additional advantage provided is the increased throughput. A detailed treatment of slotted ALOHA protocols is provided by L. G. Roberts in xe2x80x9cALOHA packet system with and without slots and capture,xe2x80x9d Computer Communication Review, vol. 5, pp. 28-42, April 1975 and is incorporated herein by reference. The simplest version of the two approaches share a common process where the corresponding receiver of the packet acknowledges the transmitter the integrity of the transmitted packet which will be destroyed when overlapping transmissions from more than one transmitter occurs.
Another MAC algorithm is called Carrier Sense Multiple Access (CSMA), with its two most common versions as discussed here. The first is called 1-persistent CSMA which allows a transmitting device to first listen to the channel to determine if another device is transmitting at that moment. If the channel is busy, the node device waits until the channel becomes idle. When the station detects an idle channel, it transmits its packet. However, due to signal propagation delay, collisions still occur, as a channel may seem to be idle from pending transmitters that will then transmit their packets at approximately about the same time.
The second version is nonpersistent CSMA. In this framework, before sending, a device senses the channel and if no other device is using the channel, the devices will begin to transmit as in 1-persistent CSMA. However, if the channel is already in use, the station will not seize the channel immediately upon detecting of the end of the previous transmission. Instead, it waits for a random period of time and then starts to transmit.
These and other present implementations of MAC layer protocols lack the capabilities to support low-latency as well as throughput of protocol and data transmissions all on the same broadcast channel. Accordingly, there is a need for a reliable Medium Access Control protocol and method suitable for use in a centralized managed network system which improves bandwidth usage, improves throughput as well as latency of both protocol and data transmissions, and provides a set of failure-recovery methods. The present invention satisfies these needs, as well as others, and generally overcomes the deficiencies found in the background art.
The present invention is a Medium Access Control (MAC) protocol and method for use in a network system employing centralized management of a common channel which is shared for protocol messages as well as data transmissions. The invention employs a modified slotted-ALOHA mode and a regular TDMA mode within a single TDMA frame definition. The MAC protocol improves the throughput of protocol messages, reduces the latency of data transmissions and provides a set of failure management methods.
In general, the MAC layer protocol of the present invention operates in a network system having a master device and a plurality of slave devices. More particularly, the MAC layer protocol is a software protocol provided and executed in the MAC sublayer of the Data Link layer according to the Open System Interconnect (OSI) standard. The Logical Link Control (LLC) sublayer forms the xe2x80x9ctopxe2x80x9d or xe2x80x9cupperxe2x80x9d half of the Data Link layer and provides virtual linking services. The MAC sublayer forms the xe2x80x9cbottomxe2x80x9d or xe2x80x9clowerxe2x80x9d half of the Data Link layer and provides the services described herein. The software protocol is executed and operates on circuitry or like hardware as is known in the art within the master and slave devices on the network at the MAC layer.
The software architecture of the present invention includes a protocol xe2x80x9cenginexe2x80x9d component and a protocol xe2x80x9cmicrocodexe2x80x9d component. The xe2x80x9cenginexe2x80x9d component, which consists of software and hardware parts, provides the execution of the microcode component and hardware-related routines and interfaces necessary at the MAC layer, including, for example, hardware set and reset routines, interfaces to the Physical (PHY) layer, and interfaces to the data transfer hardware.
The microcode component provides the actual software implementation for the protocol. The microcode component provides the engine component with the necessary software instructions, routines and other software definitions necessary to perform the protocol tasks of the present invention. This bifurcated protocol architecture allows updates to one component to be made independently of the other component, thereby streamlining the process of protocol updates. For example, updates to the microcode can be carried out by transferring the updated microcode software to a flash memory device. The engine component is then capable of executing the updated microcode by accessing the flash memory device. Similarly, the software part of the engine component is available for updates.
The invention employs centralized management of xe2x80x9cconnection-oriented service,xe2x80x9d where the establishment of a connection between the source and destination device is achieved through a master device which carries out the operation of authorizing or otherwise managing all protocol communication between the source and destination slave devices.
The present invention also provides a Time Division Multiple Access (TDMA) frame definition for the exchange of protocol messages and other network data which is managed by the master device. In general, the master device carries out the operation of controlling and managing access to the TDMA frame and its sections. Before transmitting any network data on the TDMA frame, a requesting or source slave device must first register with the master device and then request authorization to establish a data link with a target device from the master device. Responsive to this data link request, the master verifies that the requested bandwidth is available within the network and that the target device is available to communicate with the requesting device, and then authorizes a data link between the requesting device and the target device. This arrangement provides for centralized management of the shared network transport between the various devices of the network.
By way of example, and not of limitation, the MAC protocol divides data transmission time into discrete data xe2x80x9cframesxe2x80x9d employing a Time Division Multiple Access (TDMA) frame definition. Frames are further subdivided into xe2x80x9csectionsxe2x80x9d. In a presently preferred embodiment, the TDMA frame comprises a Start-Of-Frame section (SOF), a command section, and a data slot section having a plurality of variable-length data slots. The SOF section is used by the master device for defining the start of each new frame so that each slave device can synchronize with the frame structure as set forth by the master device. Additionally, the SOF section may include codes for synchronizing clocks in the slave devices to the master clock in the master device. In the preferred embodiment, the master device transmits a unique bit code symbol, which does not appear anywhere else within the frame in the SOF section, to identify the start of each new frame. The unique bit code symbols are used by each of the slave devices on the network to ascertain the beginning of each frame from the incoming data stream.
The command section of the frame is used by the node devices of the network for exchanging protocol messages. Generally, a response to a message in the command section is transmitted in the command section of the next immediate frame. In the presently preferred embodiment, the command section operates in a xe2x80x9cslotted ALOHAxe2x80x9d mode and in a regular xe2x80x9cTDMAxe2x80x9d mode as managed by the master device. A detailed treatment of slotted ALOHA protocols is provided by L. G. Roberts in xe2x80x9cALOHA packet system with and without slots and capture,xe2x80x9d Computer Communication Review, vol. 5, pp. 28-42, April 1975 and is incorporated herein by reference. The present invention employs a modified slotted ALOHA protocol as described herein. The slotted ALOHA mode is used by the master device to invite protocol messages from the slave devices. For example, a first slave device may respond to an ALOHA command with a message requesting a data link with a second device in order to transmit data to the second slave device. Other responses to an ALOHA command may include a message indicating the device is starting up, shutting down, or is busy. Other protocol message replies or commands as is known in the art may also be used.
The data slots are used for data transmission between the devices of the network. Generally, the master device dynamically assigns a data slot to a slave device which is requesting to transmit data. The data slot assignment usually comprises a start time for transfer (slot start time) and a length of time for transfer (slot length). The slot start time corresponds to the time position within the data slot section of the frame at which point the device begins its transmission. The slot length measured from the slot start provides the time position within the frame at which transmission is terminated for that the frame. The slot length corresponds to the bandwidth allocated to the device within the data section of the frame.
The flow of protocol messages communicated between the devices on the network is governed by an approach called the sequence retransmission request (SRQ) protocol. In this framework all slave devices participating in the network are structured and configured as finite-state machines, each having at least an offline state, an online state and an engaged state. The protocol messages communicated between the slave and the master devices are considered xe2x80x9cstate-changing messagesxe2x80x9d. Also defined by the SRQ protocol approach are a plurality of protocol sequences including, for example, the registration (discovery) sequence, the link request sequence, the link termination sequence, confirmation sequence, etc., where each protocol sequence includes several transmissions of protocol messages. Effectiveness and success of the transmission of a protocol sequence are acknowledged at the completion of the entire protocol sequence rather than immediately after the transmission of each message as in the traditional Automatic Retransmission reQuest (ARQ) approach. Because a protocol sequence may include a plurality of protocol messages, the overhead associated with acknowledging each protocol message is avoided, and bandwidth use is improved thereby. As noted above, protocol messages are issued in the command section of the TDMA frame.
In the present invention, the positive or negative acknowledgement of the success of a protocol sequence is communicated via a state change of the target device. Confirmation of the state change is preformed through the confirmation sequence made available to the requesting device. From this confirmation sequence, the requesting device will be notified if the desired state of the target device is not achieved which will then trigger the requesting device to repeat the past protocol sequence. The process is repeated until the desired state is achieved.
In another aspect of the present invention, the MAC protocol software provides failure-recovery methods for handling protocol sequence failure as well as non-protocol-related errors, for instance due to power failure or interfering signals. The MAC protocol provides routines which allow the master device to detect and maintain the state of each slave device. Generally, each slave device carries out the operation of ascertaining and maintaining its internal state. The slave devices also periodically communicates its state to the master device in response to an xe2x80x9cALOHAxe2x80x9d message or a xe2x80x9cPOLLxe2x80x9d message from the master device. The master device carries out the operation of ascertaining and maintaining information about the state of all slave devices on the network from the state information provided by the slave device. This state information is normally stored on a master state table residing within the MAC layer of the master device.
The master device will periodically issue a xe2x80x9cPOLLxe2x80x9d message in the command section directed at registered slave devices. Responsive to this POLL command, a registered slave device issues a reply indicating its current state. This method ensures that the master state table contains the most current information about the state of all slave devices, thereby avoiding transmissions to devices that are unavailable when requests are made by a source device to the master device.
Also included is the failure-recovery mechanism which detects, and recovers from, errors occurring at the protocol packets that may occur when protocol messages collide. Protocol collisions arise when two or more slave devices issue a reply to the master device in response to an ALOHA broadcast from the master device. Collisions are detected by error-checking functions as in known in the art within the master device.
In a presently preferred embodiment, collisions are resolved using random-delay functions within the slave devices. A collision is detected by a slave device when the master device fails to respond to the slave device""s protocol request because the master device will not respond to collided/corrupted protocol messages. When a slave detects a collision due to its protocol message, the slave device will generate a random number which dictates when the slave device may respond to an ALOHA message. For example, if the random number generated by the slave device is a three (3), the slave device will wait for three ALOHA messages before responding with its pending protocol message.
In alternative embodiment, collisions are resolved with collision-resolving function in the master device. When a collision is detected by the master device, the collision-resolving algorithm provides a subset list of slave devices to which the master device directs subsequent ALOHA broadcasts. Various searching and selecting methods known in the art may be used to generate the subset list of slave devices. This process of broadcasting to smaller subset lists of slave devices continues until collisions are no longer detected.
Another failure-recovery function provided in the invention comprises procedures for recovering from burst errors. Burst errors arise when sources outside of the network introduce signals within the transport medium thereby corrupting one or more frames. The xe2x80x9cPOLLxe2x80x9d and xe2x80x9cALOHAxe2x80x9d commands issued by the master device for managing the slave devices, the master state table and the failure-handling functions as described above for verifying protocol exchange error are normally sufficient to handle random errors within the command section but are not sufficient to handle burst errors. Burst errors corrupt the synchronization information in the SOF section. The invention provides that devices that are currently undergoing a state-transition are reverted to the previous original state of the device. Furthermore, devices that cannot receive the framing and clocking synchronization codes in the SOF section are changed to the xe2x80x9cofflinexe2x80x9d state after a predetermined amount of time subsequent to the detected corruption within the SOF section. Thereafter devices can attempt to synchronize with the master device to reestablish xe2x80x9conlinexe2x80x9d status.
The invention also provides commands for controlling power in the devices of the network, which are also issued in the command section of the frame. The power control commands provide instructions for the transmit gain controllers within each network device to maintain the minimum transmit signal strengths required from one slave device to reach its corresponding partner slave devices on the network as well as to reach the master device. These power control features are particularly helpful in wireless networks in order to reduce power consumption and reduce wireless transmission interference.
The MAC protocol of the present invention may be utilized in various network configurations and topologies including, for example, guided or wired media as well as unguided or wireless media. The MAC protocol is particularly advantageous in wireless network configurations because of the error-correction and communication management features provided by the invention. Such an illustrative wireless network is a synchronous wireless network comprising a plurality of transceiver devices transmitting and receiving pulses using a baseband or xe2x80x9cultra wide bandxe2x80x9d transport. Under this network configuration the MAC protocol and method of the present invention provide communication management, flow control, and failure-recovery for the shared air transport medium.
An object of the invention is to provide a Medium Access Control protocol which overcomes the deficiencies in the prior art.
Another object of the invention is to provide a Medium Access Control protocol which comprises a microcode component providing the protocol level functions and an engine component providing device level functions and execution support for the microcode component.
Another object of the invention is to provide a Medium Access Control protocol and method for use in a network system which allows for centralized management of all MAC-level communication by a master device.
Another object of the invention is to provide a Medium Access Control protocol and method for use in a network system which provides a sequence retransmission request protocol scheme in a network comprising finite-state machine devices.
Another object of the invention is to provide a Medium Access Control protocol and method for use in a network system where the protocol and data transmission share the same transport channel which provides an improved protocol sequence throughput via a the sequence retransmission request protocol scheme.
Another object of the invention is to provide a Medium Access Control protocol and method for use in a network system where the protocol and data transmission share the same transport channel which provides an improved latency of both the protocol as well as the data transmissions.
Another object of the invention is to provide a Medium Access Control protocol and method for use in a network system which provide dynamic allocation of transmit data slots within a Time Division Multiple Access frame definition.
Another object of the invention is to provide a Medium Access Control protocol and method for use in a network system which provides failure-recovery functions and methods.
Another object of the invention is to provide a Medium Access Control protocol and method for use in a network system which provides power control functions.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing the preferred embodiment of the invention without placing limitations thereon.